package com.tyrone.leetcode.weekgame;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author yelong.xie
 * @date 2024/2/17 22:34
 */
public class MaxOperations {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxOperations(new int[]{1,2,3,3,2,1}));
    }

    static class Solution {
        Map<String, Integer> cache = new HashMap<>();

        public int maxOperations(int[] nums) {
            boolean all = true;
            for (int i = 1; i < nums.length; i++) {
                if (nums[0]!=nums[i]) all = false;
            }
            if (all){
                return nums.length/2;
            }

            int i =0,j= nums.length-1;

            while (i<j){
                if (nums[i]!=nums[j]){
                    all = false;
                    break;
                }
                i++;j--;
            }
            if (all){
                return nums.length/2;
            }

            int before = dfs(nums[0] + nums[1], 2, nums.length - 1, nums)+1;
            int last = dfs(nums[nums.length - 2] + nums[nums.length - 1], 0, nums.length - 3, nums)+1;
            int mid = dfs(nums[0] + nums[nums.length - 1], 1, nums.length - 2, nums)+1;
            return Math.max(before, Math.max(last, mid));
        }

        /**
         * @param target
         * @param i      有效范围开始
         * @param j      有效范围结束
         * @param nums
         * @return
         */
        private int dfs(int target, int i, int j, int[] nums) {
            if (i < 0 || i >= nums.length || j < 0 || j >= nums.length || i >= j)
                return 0;
            if (cache.containsKey(target + "-" + i + "-" + j)) return cache.get(target + "-" + i + "-" + j);
            //删除前两个
            int before = 0;
            if (target == nums[i] + nums[i + 1] && i >= 0 && i < nums.length - 1) {
                before = dfs(target, i + 2, j, nums) + 1;
            }

            int last = 0;
            if (target == nums[j] + nums[j - 1] && j >= 1 && j < nums.length) {
                last = dfs(target, i, j - 2, nums) + 1;
            }
            int mid = 0;
            if (target == nums[i] + nums[j] && i >= 0 && i < nums.length && j < nums.length) {
                mid = dfs(target, i + 1, j - 1, nums) + 1;
            }
            int max = Math.max(last, Math.max(mid, before));
            cache.put(target + "-" + i + "-" + j, max);
            return max;
        }
    }
}
